package practice_2025_9.practice_9_25;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    int m = 0;
    int n = 0;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};

    /**
     * 岛屿的最大面积
     * @param grid
     * @return
     */
    public int maxAreaOfIsland(int[][] grid) {
        //  bfs
        // 有 1 -> 存在岛屿 -> 计算面积 -> 将其修改为0（防止再次遍历）
        m = grid.length;
        n = grid[0].length;
        int res = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int tmp = bfs(grid, i, j);
                    // System.out.println(tmp + " i: " + i + " j: " + j);
                    res = Math.max(res, tmp);
                }
            }
        }
        return res;
    }
    public int bfs(int[][] grid, int x, int y) {
        if (x < 0 || x > m || y < 0 || y > n) {
            return 0;
        }
        // 使用 队列 辅助优先级遍历
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        grid[x][y] = 0;
        int res = 0;
        while(!queue.isEmpty()) {
            int sz = queue.size();
            // res++;
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                int curX = tmp[0];
                int curY = tmp[1];
                res++;
                for(int i = 0; i < dx.length; i++) {
                    int nextX = curX + dx[i];
                    int nextY = curY + dy[i];
                    if (nextX >= 0 && nextX < m
                            && nextY >= 0 && nextY < n
                            && grid[nextX][nextY] == 1 ) {
                        queue.add(new int[]{nextX, nextY});
                        grid[nextX][nextY] = 0;
                    }
                }
            }
        }
        return res;
    }

    /**
     * 合并区间
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        // 合并所有区间, 返回一个不重叠的区间数组，数组恰好覆盖输入中所有区间
        if (intervals.length == 1) {
            return intervals;
        }
        Arrays.sort(intervals, (int[] v1, int[] v2) -> v1[0] - v2[0]);
        ArrayList<int[]> list = new ArrayList<>();
        int begin = intervals[0][0], end = intervals[0][1];
        for(int i = 1; i < intervals.length; i++) {
            if (end >= intervals[i][0]) {
                end = Math.max(intervals[i][1], end);
            } else {
                list.add(new int[]{begin, end});
                begin = intervals[i][0];
                end = intervals[i][1];
            }
        }
        list.add(new int[]{begin, end});
        return list.toArray(new int[list.size()][]);
    }
}